/**
 * vim: set ts=4 sw=4 tw=99 noet :
 * =============================================================================
 * SourceMod
 * Copyright (C) 2004-2009 AlliedModders LLC.  All rights reserved.
 * =============================================================================
 *
 * This program is free software; you can redistribute it and/or modify it under
 * the terms of the GNU General Public License, version 3.0, as published by the
 * Free Software Foundation.
 * 
 * This program is distributed in the hope that it will be useful, but WITHOUT
 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS
 * FOR A PARTICULAR PURPOSE.  See the GNU General Public License for more
 * details.
 *
 * You should have received a copy of the GNU General Public License along with
 * this program.  If not, see <http://www.gnu.org/licenses/>.
 *
 * As a special exception, AlliedModders LLC gives you permission to link the
 * code of this program (as well as its derivative works) to "Half-Life 2," the
 * "Source Engine," the "SourcePawn JIT," and any Game MODs that run on software
 * by the Valve Corporation.  You must obey the GNU General Public License in
 * all respects for all other code used.  Additionally, AlliedModders LLC grants
 * this exception to all derivative works.  AlliedModders LLC defines further
 * exceptions, found in LICENSE.txt (as of this writing, version JULY-31-2007),
 * or <http://www.sourcemod.net/license.php>.
 */

#ifndef _INCLUDE_SOURCEMOD_CORE_SYMBOLTABLE_H_
#define _INCLUDE_SOURCEMOD_CORE_SYMBOLTABLE_H_

#include <stdlib.h>
#include <string.h>
#include <limits.h>

#define KESTRING_TABLE_START_SIZE 65536

struct Symbol
{
    size_t length;
    uint32_t hash;
    void *address;
    Symbol *tbl_next;

    inline char *buffer()
    {
        return reinterpret_cast<char *>(this + 1);
    }
};

class SymbolTable
{
public:
    ~SymbolTable()
    {
        for (uint32_t i = 0; i < nbuckets; i++)
        {
            Symbol *sym = buckets[i];
            while (sym != NULL)
            {
                Symbol *next = sym->tbl_next;
                free(sym);
                sym = next;
            }
        }
        free(buckets);
    }

    bool Initialize()
    {
        buckets = (Symbol **)malloc(sizeof(Symbol *) * KESTRING_TABLE_START_SIZE);
        if (buckets == NULL)
        {
            return false;
        }
        memset(buckets, 0, sizeof(Symbol *) * KESTRING_TABLE_START_SIZE);

        nbuckets = KESTRING_TABLE_START_SIZE;
        nused = 0;
        bucketmask = KESTRING_TABLE_START_SIZE - 1;
        return true;
    }

    static inline uint32_t HashString(const char *data, size_t len)
    {
        #undef get16bits
        #if (defined(__GNUC__) && defined(__i386__)) || defined(__WATCOMC__) \
                || defined(_MSC_VER) || defined (__BORLANDC__) || defined (__TURBOC__)
            #define get16bits(d) (*((const uint16_t *) (d)))
        #endif
        #if !defined (get16bits)
            #define get16bits(d) ((((uint32_t)(((const uint8_t *)(d))[1])) << 8)\
                                             +(uint32_t)(((const uint8_t *)(d))[0]) )
        #endif
        uint32_t hash = len, tmp;
        int rem;

        if (len <= 0 || data == NULL)
        {
            return 0;
        }

        rem = len & 3;
        len >>= 2;

        /* Main loop */
        for (;len > 0; len--) {
                hash    += get16bits (data);
                tmp     = (get16bits (data+2) << 11) ^ hash;
                hash     = (hash << 16) ^ tmp;
                data    += 2 * sizeof (uint16_t);
                hash    += hash >> 11;
        }

        /* Handle end cases */
        switch (rem) {
                case 3: hash += get16bits (data);
                                hash ^= hash << 16;
                                hash ^= data[sizeof (uint16_t)] << 18;
                                hash += hash >> 11;
                                break;
                case 2: hash += get16bits (data);
                                hash ^= hash << 11;
                                hash += hash >> 17;
                                break;
                case 1: hash += *data;
                                hash ^= hash << 10;
                                hash += hash >> 1;
        }

        /* Force "avalanching" of final 127 bits */
        hash ^= hash << 3;
        hash += hash >> 5;
        hash ^= hash << 4;
        hash += hash >> 17;
        hash ^= hash << 25;
        hash += hash >> 6;

        return hash;

        #undef get16bits
    }

    Symbol **FindSymbolBucket(const char *str, size_t len, uint32_t hash)
    {
        uint32_t bucket = hash & bucketmask;
        Symbol **pkvs = &buckets[bucket];

        Symbol *kvs = *pkvs;
        while (kvs != NULL)
        {
            if (len == kvs->length && memcmp(str, kvs->buffer(), len * sizeof(char)) == 0)
            {
                return pkvs;
            }
            pkvs = &kvs->tbl_next;
            kvs = *pkvs;
        }

        return pkvs;
    }

    void ResizeSymbolTable()
    {
        uint32_t xnbuckets = nbuckets * 2;
        Symbol **xbuckets = (Symbol **)malloc(sizeof(Symbol *) * xnbuckets);
        if (xbuckets == NULL)
        {
            return;
        }
        memset(xbuckets, 0, sizeof(Symbol *) * xnbuckets);
        uint32_t xbucketmask = xnbuckets - 1;
        for (uint32_t i = 0; i < nbuckets; i++)
        {
            Symbol *sym = buckets[i];
            while (sym != NULL)
            {
                Symbol *next = sym->tbl_next;
                uint32_t bucket = sym->hash & xbucketmask;
                sym->tbl_next = xbuckets[bucket];
                xbuckets[bucket] = sym;
                sym = next;
            }
        }
        free(buckets);
        buckets = xbuckets;
        nbuckets = xnbuckets;
        bucketmask = xbucketmask;
    }

    Symbol *FindSymbol(const char *str, size_t len)
    {
        uint32_t hash = HashString(str, len);
        Symbol **pkvs = FindSymbolBucket(str, len, hash);
        return *pkvs;
    }

    Symbol *InternSymbol(const char* str, size_t len, void *address)
    {
        uint32_t hash = HashString(str, len);
        Symbol **pkvs = FindSymbolBucket(str, len, hash);
        if (*pkvs != NULL)
        {
            return *pkvs;
        }

        Symbol *kvs = (Symbol *)malloc(sizeof(Symbol) + sizeof(char) * (len + 1));
        kvs->length = len;
        kvs->hash = hash;
        kvs->address = address;
        kvs->tbl_next = NULL;
        memcpy(kvs + 1, str, sizeof(char) * (len + 1));
        *pkvs = kvs;
        nused++;

        if (nused > nbuckets && nbuckets <= INT_MAX / 2)
        {
            ResizeSymbolTable();
        }

        return kvs;
    }
private:
    uint32_t nbuckets;
    uint32_t nused;
    uint32_t bucketmask;
    Symbol **buckets;
};

#endif //_INCLUDE_SOURCEMOD_CORE_SYMBOLTABLE_H_

